//
//  DS_Define.h
//  DS_Demo
//
//  Created by apple on 2023/9/28.
//

#ifndef DS_Define_h
#define DS_Define_h

#include "DS_Macro.h"

/* 线性表 */
// 静态顺序表
typedef struct{
    LElemType data[MAXSIZE];
    int length;
}SqList;

//动态顺序表
typedef struct{
    LElemType *data;
    int MaxSize,length;
}DSqList;

// 单链表
typedef struct LNode{
    LElemType data;
    struct LNode *next;
}LNode,*LinkList;

// 双链表
typedef struct DNode{
    LElemType data;            // 存放链表结点数据
    struct DNode *prior,*next; // prior指向前驱链表元素，next指向后继链表元素
}DNode,*DLinkList;

// 静态链表
typedef struct{
    LElemType data;           // 存储数据元素
    int next;                 //下一个元素的数组下标
}SLinkList[MAXSIZE];
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 栈 */
// 静态顺序栈
typedef struct{
    SElemType data[MAXSIZE]; // 存放栈中元素
    int top;                 // 栈顶指针
}SqStack;

// 动态顺序栈
typedef struct{
    SElemType *base;         // 栈基指针
    SElemType *top;          // 栈顶指针
    int size;                // 栈大小
}DSqStack;

// 链栈
typedef struct LinkNode{
    SElemType data;         // 数据域
    struct LinkNode* next;  // 指针域
}*LinkStack;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 队列 */
// 静态顺序队列
typedef struct{
    QElemType data[MAXSIZE];// 存放队列元素
    int front,rear;         // 队列头指针和尾指针
}SqQueue;

// 动态顺序队列
typedef struct{
    QElemType *base;        // 初始化的动态分配空间
    int front;              // 头指针，若队列不空，指向队列头元素
    int rear;               // 尾指针，若队列不空，指向队列尾元素
}DSqQueue;

// 链队
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front; // 头指针
    QueuePtr rear; // 尾指针
}LinkQueue;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 串 */
// 静态顺序串
typedef struct{
    char ch[MAXSIZE];
    int length;
}SString;

// 堆分配顺序串
typedef struct{
    char* ch;
    int length;
}HString;

// 块链串
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct{
    Chunk *head,*tail;                   // 串的头指针和尾指针
    int curLen;                          // 当前串的长度
}LString;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 矩阵 */
// 稀疏矩阵的三元组表示
typedef struct{
    int i,j;                             // 该非零元的行下标和列下标
    MElemType e;
}Triple;
typedef struct{
    Triple data[MAXSIZE+1];              // 非零元三元组表，data[0]未用
    int mu,nu,tu;                         // 矩阵的行数、列数和非零元素个数
}TSMatix;

// 静态顺序矩阵
typedef struct{
    int row,col;                         // 矩阵的行数和列数
    MElemType data[MAXSIZE][MAXSIZE];    // 存放矩阵元素
}SqMatrix;

// 动态顺序矩阵
typedef struct{
    int row, col;                        // 矩阵的行数和列数
    MElemType **data;
}DSqMatrix;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 树 */
//顺序二叉树
typedef TElemType SqBiTree[MAX_TREE_SIZE];

//二叉链表树
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;      // 左右孩子指针
}BiTNode,*BiTree;

// 线索二叉树
typedef enum PointerTag{Link=0, Thread}PointerTag; // Link==0,表示指针，Thread==1，表示线索
typedef struct BiThrNode{
    TElemType               data;
    struct BiThrNode        *lchild, *rchild;   // 左右孩子指针
    PointerTag              LTag,RTag;          // 左右标志
}BiThrNode,*BiThrTree;

// 树的孩子链表存储表示
typedef struct CTNode{
    int             child;
    struct CTNode*  next;
}*ChildPtr;
typedef struct{
    TElemType  data;
    ChildPtr   firstchild; // 孩子链表头指针
}CTBox;
typedef struct{
    CTBox    nodes[MAX_TREE_SIZE];
    int      n,r; // 结点数和根的位置
}CTree;

// 树的双亲表示法存储结构
typedef struct{
    TElemType data;
    int parent;
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;  // 结点数
}PTree;

// 树的二叉链表（左孩子右兄弟）存储表示
typedef struct CSNode{
    TElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode, *CSTree;

// 哈夫曼树和哈夫曼编码的存储表
typedef struct{
    unsigned int        weight; // 权重
    unsigned int        parent,lchild,rchild;
}HTNode,*HuffmanTree; // 动态分配数组存储哈夫曼树
typedef char* *HuffmanCode; // 动态分配数组存储哈夫曼编码表
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


/* 图 */
//邻接矩阵
typedef struct{
    VertexType Vex[MAXVERTEXNUM]; // 顶点表
    EdgeType Edge[MAXVERTEXNUM][MAXVERTEXNUM]; // 邻接矩阵，边表
    int vexnum,arcnum; // 图的当前顶点数，弧数
}MGraph;

//邻接表
typedef struct ArcNode{ // 边表结点
    int adjvex; //该弧所指向的顶点的位置
    struct ArcNode *next;//指向下一条弧的指针
}ArcNode;
typedef struct VNode{ // 顶点表结点
    VertexType data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAXVERTEXNUM];
typedef struct{
    AdjList vertices; //邻接表
    int vernum, arcnum; // 图的顶点数和弧数
}ALGraph;

// 十字链表
typedef struct ArcBox{   // 边域
    int tailvex,headvex; // 该弧的尾和头顶点的位置
    struct ArcBox *hlink,*tlink; // 分别为弧头相同和弧尾相同的弧的链域
    InfoType *info;  // 该弧相关信息的指针
}ArcBox;
typedef struct VexNode{
    VertexType data;
    ArcBox *firstin, *firstout; // 分别指向该顶点第一条入弧和出弧
}VexNode;
typedef struct{
    VexNode xlist[MAXVERTEXNUM]; // 表头向量
    int vexnum,arcnum; //  有向图的顶点数和弧数
}OLGraph;

// 邻接多重表
typedef enum {unvisited, visited} VisitIf;
typedef struct EBox{ // 边域
    VisitIf mark; // 访问标志
    int ivex, jvex; // 该边依附的起点和中终点
    struct EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边
    InfoType *info; // 该边信息指针
}EBox;
typedef struct VexBox{ // 顶点域
    VertexType Data;
    EBox* firstedge;
}VexBox;
typedef struct{
    VexBox adjmulist[MAXVERTEXNUM];
    int vexnum,edgenum; // 无向图的当前顶点数和边数
}AMGraph;

/* B树 */
// 关键字antry
typedef struct{
    const char* key;
    const char* arrow;
    int value;
}Antry;
// 结点指针
typedef struct Node{
    Antry* elem;
    const struct Node** childs;
    const struct Node* parent;
}Node;

typedef struct{
    unsigned int dim;
    unsigned int min_dim;
    const Node* root;
}BTree;


#endif /* DS_Define_h */
